LeetCode 881、救生艇

一、题目描述

给定数组 people 。people[i]表示第 i 个人的体重 ，船的数量不限，每艘船可以承载的最大重量为 limit。

每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。

返回 承载所有人所需的最小船数 。

示例 1：

输入：people = [1,2], limit = 3 输出：1 解释：1 艘船载 (1, 2)

示例 2：

输入：people = [3,2,2,1], limit = 3 输出：3 解释：3 艘船分别载 (1, 2), (2) 和 (3)

示例 3：

输入：people = [3,5,3,4], limit = 5 输出：4 解释：4 艘船分别载 (3), (3), (4), (5)

提示：

• 1 <= people.length <= 5 * 10^4
• 1 <= people[i] <= limit <= 3 * 10^4

二、题目解析

三、参考代码

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:

        # 先排序
        people.sort()

        # 获取数组长度
        n = len(people)

        # 寻找两人组

        # 最左边的位置
        left = 0

        # 最右边的位置
        right = n - 1

        # 船的数量
        ans = 0

        while left <= right :
            
            # 1、如果 people[left] + people[right] <= limit
            # 说明 people[left] 和 people[right] 可以同船
           
            if people[left] + people[right] <= limit :

                #  此时船的数量加一
                ans += 1

                # 两个指针分别往中间靠拢

                left += 1

                right -= 1

                
            # 如果 people[left] + people[right] > limit
            # 说明 people[left] 和 people[right] 不可以同船
            else:

                # 由于题目说明了人的重量不会超过 limit
                # people[right] 需要独自坐船，船的数量加一
                ans += 1

                # people[right] 坐船后
                # right 需要向内移动，寻找新的组合
                right -= 1

        # 返回结果
        return ans